#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>

// 结点定义
typedef struct Node
{
    int data;
    struct Node *next;
} Node, *LinkList;

// 初始化带头结点的单链表
bool InitList(LinkList &L)
{
    L = (Node *)malloc(sizeof(Node));
    if (L == NULL)
    {
        return false;
    }
    L->next = NULL;
    return true;
}

// 判断链表是否为空
bool Empty(LinkList &L)
{
    if (L->next == NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}

// 后插操作：在p之后插入e
bool InsertNextNode(Node *p, int e)
{
    if (p == NULL)
    {
        return false;
    }
    Node *s = (Node *)malloc(sizeof(Node)); // 注意分配的是Node，不是Node*
    if (s == NULL)
    {
        return false;
    }
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

// 在第i个位置插入数据e（从1开始）
bool InsertList(LinkList &L, int i, int e)
{
    if (i < 1)
    {
        return false;
    }
    Node *p = L; // 头结点是第0个位置
    int j = 0;
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }
    return InsertNextNode(p, e);
}

// 头插法建立链表，遇-1结束
LinkList Head_Insert(LinkList &L)
{
    int x;
    Node *s;
    L = (LinkList)malloc(sizeof(Node));
    L->next = NULL;
    scanf("%d", &x);
    while (x != -1)
    {
        s = (Node *)malloc(sizeof(Node));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}

// 打印链表所有元素
void PrintList(LinkList L)
{
    Node *p = L->next;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 链表就地倒置（带头结点）
void ReverseList(LinkList &L)
{
    if (L == NULL || L->next == NULL)
    {
        return;
    }

    Node *p = L->next;
    Node *q;
    L->next = NULL;

    while (p != NULL)
    {
        q = p->next;
        p->next = L->next;
        L->next = p;
        p = q;
    }
}

// 测试函数
void test()
{
    LinkList L;
    InitList(L);
    printf("请输入链表元素（-1结束）：\n");
    Head_Insert(L);
    printf("当前链表为：\n");
    PrintList(L);

    printf("倒置后的链表为：\n");
    ReverseList(L);
    PrintList(L);

    printf("向位置3插入值99...\n");
    InsertList(L, 3, 99);
    PrintList(L);

    if (Empty(L))
        printf("链表为空\n");
    else
        printf("链表非空\n");
}

// 主函数
int main()
{
    test();
    return 0;
}
